const int maxn=1e5+100;
const int mod=1e9+7;
class Solution {
public: 
int dp[2][1<<11];
int a[maxn];
int ksm(int a,int k){
    int res=1;
    while(k)
    {
        if(k&1) res=res*a%mod;
        k>>=1;
        a=a*a%mod;
    }return res;
}
int numberOfGoodSubsets(vector<int>& nums) {
    for(int i=0;i<nums.size();i++) a[i+1]=nums[i];
    int state[31] = { 0, 0, 1, 2, 0, 4, 3, 8, 0, 0, 5, 16, 0, 32, 9, 6, 0, 64, 0, 128, 0, 10, 17, 256, 0, 0, 33, 0, 0, 512, 7 };
    int ans=0;int now=0;
    int allstate=1<<10;
    int n=nums.size();int ones=0;
    for(int i=1;i<=n;i++)
    {
        int nowstate=state[a[i]];
        if(a[i]==1) ones++;
        if(nowstate==0) continue;
        cout<<"nowstate="<<nowstate<<endl;
        dp[now][nowstate]+=1%mod;
        for(int j=0;j<allstate;j++)
        {
            if( (j&nowstate)!=0 ) continue;
            
            dp[now][j|nowstate]+=dp[now^1][j]%mod;
        
            ans+=dp[now][j|nowstate]%mod;    
        }
        cout<<"ans="<<ans<<endl;
        ///for(int j=0;j<allstate;j++) dp[now^1][j]=0;
        now^=1;
    }
    return (ans%mod*ksm(2,ones)%mod)%mod;
}
};